package com.chapter1.basic.analysis;

/** 
 * @ClassName: PathCompression 
 * @Description: 路径压缩
 * @author minjun minjun@bw30.com
 * @date 2015-2-13 下午9:15:35 
 *  
 */
public class PathCompression {

	private int[] id;
	
	private int[] size;
	
	private int count;

	public PathCompression(int count) {
		this.count=count;
		id=new int[count];
		size=new int[count];
		for(int i=0;i<count;i++){
			id[i]=i;
			size[i]=1;
		}
	}
	
	public boolean connected(int m,int n){
		return find(m)==find(n);
	}
	
	private int find(int m){
		//如果是根节点，那么m=id[m]；如果不是，那么m!=id[m]
		while(m!=id[m]){
			/**
			 * 压缩路径
			 */
			//让父节点不断上移，直至根节点
			id[m]=id[id[m]];
			//不断向上获取父节点
			m=id[m];
		}
		return m;
	}
	
	public void union(int m,int n){
		int i=find(m);
		int j=find(n);
		if(i==j) {return;}
		//如果两者不连通，那么判断两者所属的树哪个更大，将小的移到大的那一边，以便最大限度的降低树的高度
		if(size[i]<size[j]){
			//将小数的根节点指向大树
			id[i]=j;
			//将较大的树的size增加
			size[j]+=size[i];
		}else{
			id[j]=i;
			size[i]+=size[j];
		}
		count--;
	}
	
	/*------------------------------------------*/

	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}
}
